package library;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class MaxFlow {

	List<Edge> minCut;
	
	Node source,sink;
	//All nodes (it doesn't matter whether source and sink are there).
	List<Node> nodesList;
	
	public void addEdge(Node from, Node to, int capacity){
		
		Edge e = new Edge (to,capacity);
		
		Edge ee = new Edge (from,0);
		
		e.reverse=ee;
		
		ee.reverse=e;
		
		from.edges.add(e);
		
		to.edges.add(ee);
	}
	
	public int maxFlow(){
		
		int flow =0;
		
		while (bfs()){
			
			flow+=update();
		}
		
		return flow;
	}
	public int update(){
		
		int ret = Integer.MAX_VALUE;
		
		Edge current = sink.used;
		
		while (current!=null){
			
			ret = Math.min(ret, current.reverse.capacity);
			
			current = current.to.used;
		}
		
		current = sink.used;
		
		while (current!=null){
			
			current.capacity+=ret;
			
			current.reverse.capacity-=ret;
			
			current = current.to.used;
		}
		return ret;
	}
	/**
	 * BFS on flow problem
	 * @param nodesList The list of all nodes
	 * @return
	 */
	public boolean bfs(){
		
		for (Node n : nodesList){ n.marked = false; n.used =null;}
		
		Queue<Edge>queue = new LinkedList<Edge>();
		
		source.marked = true;
		
		sink.marked=false;
		
		queue.offer(new Edge(source, 0));
		
		while (!queue.isEmpty()){
			
			Edge current = queue.poll();
			
			if (current.to==sink)
				return true;
			
			for (Edge e: current.to.edges)
				
				if (e.capacity>0 && !e.to.marked){
					
					queue.offer(e);
					
					e.to.used=e.reverse;
					
					e.to.marked = true;
				}
		}
		return false;
	}
	/**
	 * Finds min cut, puts it in list minCut
	 * NOTE: IF USING UNDIRECTED GRAPH, EACH EDGE WILL APPEAR TWICE, LIKE: A A B B C C D D
	 */
	public void minCutBfs(){

		for (Node n : nodesList){ n.marked = false; n.used =null;}

		LinkedList<Edge>queue = new LinkedList<Edge>();

		source.marked = true;

		sink.marked=false;

		queue.offer(new Edge(source, 0));

		while (!queue.isEmpty()){

			Edge current = queue.poll();

			for (Edge e: current.to.edges)

				if (e.capacity>0 && !e.to.marked){

					queue.offer(e);

					e.to.used=e.reverse;

					e.to.marked = true;
				}
				else if (!e.to.marked){
					minCut.add(e);
				}
		}
		
		for(int i=0;i<minCut.size();i++)
			if(minCut.get(i).to.marked){
				minCut.remove(i);
				i--;
			}
	}
	
	class Node{
		
		Edge used;
		boolean marked;
		List<Edge> edges;
		
		public Node(){
			
			edges = new LinkedList<Edge>();
			marked = false;
		}
	}
	class Edge{
		
		int capacity;
		Edge reverse;
		Node to;
		
		public Edge (Node to, int capacity){
			
			this.to = to;
			this.capacity = capacity;
		}
	}
}
